﻿#include "SinglyLink.h"
// C/C++ 学习网站：https://legacy.cplusplus.com 注意旧版本（搜索）和新版本

single_node* create_single_node(single_node_type n)
{ // 创建单向链表节点
    single_node* p_node = (single_node*)malloc(sizeof(single_node));
    if (p_node == NULL) {
        perror("create_single_node!\n");
        return NULL;
    }
    else {
        p_node->data = n;
        p_node->next = NULL;
    }
    return p_node;
}

void printf_single_list(single_node* head)
{ // 打印单向链表,需要传入头结点
    if (head == NULL) {
        printf("链表为空！\n");
        return;
    }
    while (head->next != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("%d\n", head->data);
    head = NULL; // 手动释放无用指针，防止堆区指针可能退出函数时保留
}

void add_head_single_node(single_node** head, single_node_type n)
{ // 在单向链表头部添加节点
    single_node* p_node = create_single_node(n);
    if (p_node == NULL) { // 内存分配失败   
        perror("add_head_single_node！\n");
        return;
    }
    p_node->next = *head;
    *head = p_node;
    p_node = NULL;
    head = NULL; // 手动释放无用指针，栈区指针，不用释放也行
    //printf("添加头部节点成功！\n");
}

void del_head_single_node(single_node** head)
{ // 删除单向链表头部节点
    if (*head == NULL) { // 链表为空
        printf("链表为空！\n");
        return;
    }
    single_node* p_node = *head;
    *head = p_node->next;
    p_node->next = NULL;
    free(p_node);
    p_node = NULL;
    head = NULL; // 手动释放无用指针
    //printf("删除头部节点成功！\n");
}

void add_end_single_node(single_node** head, single_node_type n)
{ // 在单向链表尾部添加节点
    single_node* p_node = create_single_node(n);
    if (p_node == NULL) { // 内存分配失败
        perror("add_end_single_node！\n");
        return;
    }
    if (*head == NULL) // 链表为空，则头结点指向新节点
        *head = p_node;
    else {
        single_node* p_cursor = *head;
        while (p_cursor->next != NULL)
            p_cursor = p_cursor->next;
        p_cursor->next = p_node;
        //p_node->next = NULL;  // 本来就是 NULL
        p_node = NULL;
        p_cursor = NULL;
        //printf("添加尾部节点成功！\n");
    }
    head = NULL; // 手动释放无用指针
}

void del_end_single_node(single_node** head)
{ // 删除单向链表尾部节点
    if (*head == NULL) { // 链表为空
        printf("链表为空！\n");
        return;
    }
    single_node* p_cursor = *head; // cursor 意为游标
    if (p_cursor->next == NULL) { // 链表只有一个节点
        *head = NULL;
        free(p_cursor);
        p_cursor = NULL;
        return;
    }
    single_node* p_next = p_cursor->next;
    while (p_next->next != NULL)
    {
        p_cursor = p_cursor->next;
        p_next = p_cursor->next;
    }
    p_cursor->next = NULL; // 可以不写，建议写上，防止堆区指针可能退出函数时保留
    p_cursor = NULL;
    //p_next->next = NULL; // 循环结束后，p_next 指向尾节点，其 next 指针本来就是 NULL
    free(p_next);
    p_next = NULL;
    head = NULL; // 手动释放无用指针
    //printf("删除尾部节点成功！\n");
}

size_t get_single_list_len(single_node* head)
{ // 获取单向链表长度
    if (head == NULL)
        return 0;
    size_t len = 1;
    while (head->next != NULL) {
        head = head->next;
        ++len;
    }
    head = NULL; // 手动释放无用指针
    return len;
}

void insert_single_node(single_node** head, size_t index, single_node_type n)
{ // 在单向链表指定位置插入节点
    if (index < 0 || index > get_single_list_len(*head)) { // 索引超出范围
        printf("节点位置超出范围！节点插入失败\n");
        return;
    }
    if (index == 0) { // 插入到头部
        add_head_single_node(head, n);
        return;
    }
    else if (index == get_single_list_len(*head)) // 插入到尾部
        add_end_single_node(head, n);
    else {
        single_node* p_node = create_single_node(n);
        if (p_node == NULL) { // 内存分配失败
            perror("insert_single_node！\n");
            return;
        }
        single_node* p_cursor = *head;
        int i;
        for (i = 1; i < index; ++i)
            p_cursor = p_cursor->next;
        p_node->next = p_cursor->next;
        p_cursor->next = p_node;
        p_node = NULL;
        p_cursor = NULL;
    }
    head = NULL; // 手动释放无用指针
    //printf("在 %d 位置插入节点数据 %d 成功！\n", index, n);
}

void del_single_node(single_node** head, size_t index)
{ // 删除单向链表指定位置节点
    if (index < 1 || index > get_single_list_len(*head)) { // 索引超出范围
        printf("节点位置超出范围！节点删除失败\n");
        return;
    }
    if (index == 1) // 删除头部节点
        del_head_single_node(head);
    else {
        single_node* p_cursor = *head;
        int i;
        for (i = 1; i < index - 1; ++i)
            p_cursor = p_cursor->next;
        single_node* p_del = p_cursor->next;
        p_cursor->next = p_del->next;
        p_del->next = NULL;
        free(p_del);
        p_del = NULL;
    }
    head = NULL; // 手动释放无用指针
    //printf("删除 %d 位置节点成功！\n", index);
}

int del_num_single_list(single_node** head, single_node_type num)
{ // 删除单向链表中的一个数据，返回其位置
    if (head == NULL) {
        printf("链表为空！\n");
        return -1; // 链表为空
    }
    single_node* p_cursor = *head;
    if ((*head)->data == num) // 链表头结点就是要删除的数据
    {
        (*head) = (*head)->next;
        p_cursor->next = NULL;
        free(p_cursor);
        p_cursor = NULL;
        return 1;
    }
    int index = 1;
    single_node* p_del = p_cursor;
    while (p_cursor->next != NULL)
    {
        p_cursor = p_cursor->next;
        ++index;
        if (p_cursor->data == num)
        {
            p_del->next = p_cursor->next; // 找到要删除的数据，前一个节点指向当前节点的下一个节点
            p_cursor->next = NULL; // 当前节点的 next 指针指向 NULL
            free(p_cursor); // 释放当前节点内存
            p_cursor = NULL; // 手动释放无用指针
            p_del = NULL; // 手动释放无用指针
            //printf("在 %d 位置删除数据 %d\n", index, num);
            return index;
        }
        else
            p_del = p_del->next; // p_del 指向前一个节点
    }
    printf("没有找到数据 %d\n", num);
    head = NULL; // 手动释放无用指针
    p_del = NULL; // 手动释放无用指针
    return -1; // 没有找到数据
}

void reverse_single_list1(single_node** head)
{ // 反转单向链表，这里使用迭代方式
    if (*head == NULL) // 链表为空
        return;
    single_node* p_prev = *head; // 前驱节点，初始指向头结点
    if (p_prev->next == NULL) // 链表只有一个节点
        return;
    single_node* p_cursor = p_prev->next; // 游标节点，初始指向头结点的下个节点
    if (p_cursor->next == NULL) // 链表只有两个节点
    {
        p_prev->next = NULL;
        p_cursor->next = p_prev;
        (*head) = p_cursor;
        p_prev = NULL;  // 手动释放无用指针
        p_cursor = NULL; // 手动释放无用指针
        return;
    }
    single_node* p_next = NULL; // 后继节点，初始为空
    while (p_cursor->next != NULL) {
        p_next = p_cursor->next; // 后继节点指向游标节点的下个节点
        p_cursor->next = p_prev;  // 游标节点的 next 指向前驱节点
        p_prev = p_cursor;  // 前驱节点后移
        p_cursor = p_next;  // 游标节点后移
    }
    (*head)->next = NULL;// 循环结束后，头节点变成了尾节点，next 指针需要重新指向 NULL
    p_cursor->next = p_prev; // 最后一个节点的 next 指针指向前驱节点，完成连接
    *head = p_cursor; // 头结点指向最后一个节点，完成反转
    //p_next->next = NULL; // 这里本来就是 NULL
    p_next = NULL; // 堆区指针退出函数可能保留，这里手动释放无用指针
    p_cursor = NULL; // 这里手动释放无用指针
    p_cursor = NULL; // 释放无用指针
    p_prev = NULL; // 释放无用指针
    //printf("反转单向链表成功！\n");
}

single_node* reverse_single_list2(single_node* head)
{ // 反转单向链表，这里使用递归方式
    if (head->next == NULL) // 链表只有一个节点
        return head;
    single_node* new_head = reverse_single_list2(head->next);
    // 递归调用，保持最后一个节点
    single_node* prev = head->next; // 保存当前节点的递归返回节点（下一个节点）
    prev->next = head; // 将下一个节点连接到当前节点
    //((head->next)->next) = head; // 写成这样编译不过去
    head->next = NULL; // 连接完成后，当前节点是尾节点，需要将 next 指针指向 NULL
    return new_head; // 递归返回新链表的头结点（旧链表的尾结点）
}

int search_num_single_list(single_node* head, single_node_type num)
{ // 在单向链表中查找一个数据，返回其位置
    if (head == NULL) {
        printf("链表为空！\n");
        return -1; // 链表为空
    }
    int index = 1;
    while (head->next != NULL)
    {
        if (head->data == num)
        {
            printf("在 %d 位置找到数据 %d\n", index, num);
            return index;
        }
        head = head->next;
        ++index;
    }
    printf("没有找到数据 %d\n", num);
    head = NULL; // 手动释放无用指针
    return -1; // 没有找到数据
}

single_node* li1_add_li2(single_node* head1, single_node* head2)
{ // 将 head2 链表追加到 head1 链表的尾部，返回合并后的链表头结点
    if (head1 == NULL) // 链表1为空
        return head2;
    else if (head2 == NULL) // 链表2为空
        return head1;
    single_node* p_cursor1 = head1;
    while (p_cursor1->next != NULL)
        p_cursor1 = p_cursor1->next;
    p_cursor1->next = head2;
    p_cursor1 = NULL; // 手动释放无用指针
    //printf("链表合并成功！\n");
    return head1; // 这里返回 head1 即可，因为 head1 已经是合并后的链表头结点

    //if (p_cursor1->data <= p_cursor2->data) // 链表 1 的头结点小于等于链表 2 的头结点
    //{
    //    p_cursor1->next = merge_single_list(p_cursor1->next, p_cursor2);
    //    return head1;
    //}
    //else // 链表2的头结点小于链表1的头结点
    //{
    //    p_cursor2->next = merge_single_list(p_cursor1, p_cursor2->next);
    //    return head2;
    //}
}

/*static void swap_single_node(single_node* p_node1, single_node* p_node2)
{ // 交换两个节点的数据
    single_node_type temp = p_node1->data;
    p_node1->data = p_node2->data;
    p_node2->data = temp;
} */

void bubble_sort_singly_linke(single_node* head)
{ // 排序单向链表，这里使用冒泡排序
    if (head == NULL || head->next == NULL) // 链表为空或只有一个节点
        return;
    single_node* p_cursor = head;
    single_node* p_next = p_cursor->next;
    single_node* 回溯指针 = NULL;  // 完全中文编程指日可待！建议替换为 回溯指针
    single_node_type temp;
    while (回溯指针 != head)
    {
        while (p_next != 回溯指针)
        {
            if (p_cursor->data > p_next->data)
            { //swap_single_node(p_cursor, p_next); // 交换
                temp = p_cursor->data;
                p_cursor->data = p_next->data;
                p_next->data = temp;
            }
            p_cursor = p_next;
            p_next = p_next->next;
        }
        回溯指针 = p_cursor; // 每次记录 p_cursor 最后的节点
        p_cursor = head; // 重置游标节点
        p_next = p_cursor->next; // 重置下一个节点
    }
    head = NULL; // 手动释放无用指针
    p_cursor = NULL; // 手动释放无用指针
    p_next = NULL; // 手动释放无用指针
    回溯指针 = NULL; // 手动释放无用指针
    //printf("排序单向链表成功！\n");
}

void destroy_single_list(single_node* head)
{ // 释放单向链表内存，单向链表的储存可能不是连续的，需要逐个释放
    single_node* p_del;
    while (head->next != NULL)
    {
        p_del = head;
        head = head->next;
        p_del->next = NULL;
        free(p_del);
        p_del = NULL;
    }
    free(head);
    head = NULL;
    printf("释放单向链表内存成功！\n");
}